from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        self.flag = False
        n = len(nums)
        if not n: return -1
        left = nums[:n >> 1]
        right = nums[n >> 1:]

        def bisect(arr, target):
            l = 0
            r = len(arr) - 1
            while l <= r:
                mid = (l + r) >> 1
                if arr[mid] == target:
                    return mid
                elif arr[mid] > target:
                    r = mid - 1
                else:
                    l = mid + 1
            return -1

        # 找到有序部分使用二分查找 若没有找到结果去搜索另一部分的旋转数组
        arrays = [left, right]
        if left[0] < left[-1]:
            index = 0
        else:
            index = 1
        arr = arrays[index]
        res = bisect(arr, target)
        if res != -1:
            self.flag = True
            return res
        add = (n >> 1) if index else 0
        return add + self.search(arrays[~index], target)


if __name__ == '__main__':
    s = Solution()
    r = s.search(nums=[4, 5, 6, 7, 0, 1, 2], target=3)
    print(r)
